Third maximum number

Time: O(N); Space: O(1); easy

Given an array of integers, return the 3rd Maximum Number in this array, if it doesn’t exist, return the Maximum Number. The time complexity must be O(N) or less.

Example 1:

Input: nums = [3, 2, 1]

Output: 1

Explanation:

• The third maximum is 1.

Example 2:

Input: nums = [1, 2]

Output: 2

Explanation:

• The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2, 2, 3, 1]

Output: 1

Explanation:

• Note that the third maximum here means the third maximum distinct number.

• Both numbers with value 2 are both considered as second maximum.

class Solution1(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        top = [float("-inf")] * 3
        for num in nums:
            if num > top[0]:
                top[0], top[1], top[2] = num, top[0], top[1]
                count += 1
            elif num != top[0] and num > top[1]:
                top[1], top[2] = num, top[1]
                count += 1
            elif num != top[0] and num != top[1] and num >= top[2]:
                top[2] = num
                count += 1

        if count < 3:
            return top[0]

        return top[2]

s = Solution1()
nums = [3, 2, 1]
assert s.thirdMax(nums) == 1
nums = [1, 2]
assert s.thirdMax(nums) == 2
nums = [2, 2, 3, 1]
assert s.thirdMax(nums) == 1

See also:

https://leetcode.com/problems/third-maximum-number

https://www.lintcode.com/problem/third-maximum-number